﻿// 0816train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <map>

using namespace std;

/*
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
 */

class Solution01 {
public:
    vector<vector<int>>result_vec;
    vector<int>track_vec;
    vector<vector<int>> subsets(vector<int>& nums) {
        backTrack(nums, 0);
        return result_vec;
    }

    void backTrack(vector<int>&nums, int start)
    {
        result_vec.push_back(track_vec);

        for (int i=start; i<nums.size(); i++)
        {
            track_vec.push_back(nums[i]);
            backTrack(nums, i + 1);
            track_vec.pop_back();

        }
	    
    }
};

class Solution02 {
public:
    vector<vector<int>>result_vec;
    vector<int>track_vec;
    vector<vector<int>> combine(int n, int k) {
        vector<int>nums(n);
        for (int i=1; i<=n; i++)
        {
            nums[i - 1] = i;
        }
        backTrack(nums, 0, k);
        return result_vec;
    }
    void backTrack(vector<int>& nums, int start, int k)
    {
        if (track_vec.size()==k)
        {
            result_vec.push_back(track_vec);
        }

        for (int i = start; i < nums.size(); i++)
        {
            track_vec.push_back(nums[i]);
            backTrack(nums, i + 1, k);
            track_vec.pop_back();

        }
    }
};


/*
 输入描述
输入为两行，第一行是每张手牌的数字，数字由空格分隔，第二张为对应的每张手牌的颜色，
用r y b g这4个字母分别代表4种颜色，字母也由空格分隔。手牌数量不超过10

输出描述
输出一个数字，即最多能打出的手牌的数量。

示例1
输入
1 4 3 4 5
r y b b r

输出
3
 */

class Solution03
{
public:
    int result = 0;
    vector<pair<int, char>>sub_pair;
    //vector<vector<pair<int, char>>>track_pair;
    void solve03(vector<pair<int,char>>&pair_vec)
    {
        int pair_vec_size = pair_vec.size();
        vector<bool>used_vec(pair_vec_size, false);
        backTrack(pair_vec, used_vec);

        cout << result;
    }

    bool checkVerify()
    {
        if (sub_pair.size() <= 1)return true;
        bool result = true;
        for (int i=1; i<sub_pair.size();i++)
        {
            bool same_first = sub_pair[i].first == sub_pair[i - 1].first;
            bool same_second = sub_pair[i].second == sub_pair[i - 1].second;

            if (!same_first && !same_second)
            {
                result = false;
                break;
            }
	        
        }
        return result;
	    //checkVerify
    }

    void backTrack(vector<pair<int, char>>& pair_vec, vector<bool>& used_vec)
    {
        if (checkVerify())
        {
            int sub_pair_size = sub_pair.size();
            result = max(result, sub_pair_size);
        }
        //track_pair.push_back(sub_pair);
        if (sub_pair.size() == pair_vec.size())
        {
            return;
        }

        for (int i=0; i<pair_vec.size(); i++)
        {
            if (used_vec[i]) continue;

            sub_pair.push_back(pair_vec[i]);
            used_vec[i] = true;
            backTrack(pair_vec, used_vec);
            sub_pair.pop_back();
            used_vec[i] = false;
        }

    }

    //Solution03
};


int main()
{
    /*
    1 4 3 4 5
	r y b b r
     */
	{
        vector<int>num_vec;
        vector<char>char_vec;

        string input;
        getline(cin, input);
        stringstream oh_sstream1(input);
        string token;
        while (oh_sstream1>>token)
        {
            num_vec.push_back(stoi(token));
        }

        getline(cin, input);
        stringstream oh_sstream2(input);
        while (oh_sstream2 >> token)
        {
            char_vec.push_back(token[0]);
        }

        //for (auto&oh_char: char_vec)
        //{
        //    cout << oh_char << ' ';
        //}
        int vec_size = num_vec.size();
        vector<pair<int, char>>pair_vec(vec_size);
        for (int i=0; i<vec_size; i++)
        {
            pair_vec[i] = make_pair(num_vec[i], char_vec[i]);
        }

        //vector<pair<int, char>>pair_vec = { {1,'r'},{4,'y'},{3,'b'},{4,'b'},{5,'r'} };

        Solution03 solu;
        solu.solve03(pair_vec);

        return 0;
	}
	{
        //输入: n = 4, k = 2
        Solution02 solu;
        vector<vector<int>>result_vec = solu.combine(4, 2);

        cout << result_vec.size();

        return 0;
	}

    //nums = [1,2,3]
    vector<int>nums = { 1,2,3 };
    Solution01 solu;
    solu.subsets(nums);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
